package C034;

/**
 * ClassName: C04
 * Package: C034
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/5 11:18
 * @Version 1.0
 * @Since 1.0
 */
public class C04 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(1);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;

        System.out.println(isPalindrome(listNode));

        while(listNode!= null) {
            System.out.println(listNode.val + " ");
            listNode = listNode.next;
        }

    }
    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }


    public static boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }

        // 快慢指针找到链表的中间的位置
        ListNode slow = head, fast = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // slow 来到中间的位置，反转后面的链表的内容
        ListNode cur = slow, pre = null, next = null;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        // cur是结尾， head 是头
        cur = pre;
        boolean res = true;
        ListNode cur2 = cur, h2 = head;
        while(cur2 != null && h2 != null) {
            if(cur2.val != h2.val) {
                res = false;
                break;
            }
            cur2 = cur2.next;
            h2 = h2.next;
        }

        // 恢复链表, cur开始
        pre = null;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return res;
    }

}
